package question8;

import java.util.LinkedList;

/**
 * @FileName Test
 * @Description
 * @Author Sword
 * @date 2024-12-04
 **/
public class Test {
    public static void main(String[] args) {
        //求解约瑟夫问题：12个人排成一圈，从1号报数，凡是数到5的人就出队列（出局），然后继续报数，试问最后一个出局的人是谁。
        int n = 12; // 总人数
        int k = 5;  // 每数到第 k 个人出局
        int lastPerson = findLastPerson(n, k);
        System.out.println("最后出局的人是: " + lastPerson);
    }

    public static int findLastPerson(int n, int k) {
        // 使用链表来模拟圆圈
        LinkedList<Integer> people = new LinkedList<>();

        // 初始化人员
        for (int i = 1; i <= n; i++) {
            people.add(i);
        }

        int index = 0; // 当前索引
        // 当链表中还有多于一人时，继续进行
        while (people.size() > 1) {
            // 计算出局的人的索引
            index = (index + k - 1) % people.size();

            System.out.print (people.get(index) + " ");

            // 移除该人
            people.remove(index);
        }

        // 返回最后剩下的人的编号
        return people.get(0);
    }
}
